We provide in particular an "example" notebook which contains a detailed presentation of For a mismatched model, the replica symmetry assumption, discussed below, is generically not valid. Note that the matrix Φ only appears in the last "delta" term. We can use a Fourier transformation of the delta terms, which allows in the end to transform eq. The infimum is again over positive symmetric (Hermitian) matrices. This term is very similar to the prior term detailed in the previous section.

In this paper, assuming a natural strengthening of the low-degree conjecture, we provide evidence of computational hardness for two problems: (1) the (partial) matching recovery problem in the sparse correlated Erd\H{o}s-R\'enyi graphs $\mathcal G(n,q;\rho)$ when the edge-density $q=n^{-1+o(1)}$ and the correlation $\rho<\sqrt{\alpha}$ lies below the Otter's threshold, solving a remaining problem in \cite{DDL23+}; (2) the detection problem between the correlated sparse stochastic block model $\mathcal S(n,\tfrac{\lambda}{n};k,\epsilon;s)$ and a pair of independent stochastic block models $\mathcal S(n,\tfrac{\lambda s}{n};k,\epsilon)$ when $\epsilon^2 \lambda s<1$ lies below the Kesten-Stigum (KS) threshold and $s<\sqrt{\alpha}$ lies below the Otter's threshold, solving a remaining problem in \cite{CDGL24+}. One of the main ingredient in our proof is to derive certain forms of \emph{algorithmic contiguity} between two probability measures based on bounds on their low-degree advantage. To be more precise, consider the high-dimensional hypothesis testing problem between two probability measures $\mathbb{P}$ and $\mathbb{Q}$ based on the sample $\mathsf Y$. We show that if the low-degree advantage $\mathsf{Adv}_{\leq D} \big( \frac{\mathrm{d}\mathbb{P}}{\mathrm{d}\mathbb{Q}} \big)=O(1)$, then (assuming the low-degree conjecture) there is no efficient algorithm $\mathcal A$ such that $\mathbb{Q}(\mathcal A(\mathsf Y)=0)=1-o(1)$ and $\mathbb{P}(\mathcal A(\mathsf Y)=1)=\Omega(1)$. This framework provides a useful tool for performing reductions between different inference tasks.

The ability of carefully designed computer programs to generate meaningful mathematical conjectures has been demonstrated since the late 1980s, notably by Fajtlowicz's GRAFFITI program [23]. Indeed, this heuristic-based program was the first artificial intelligence to make significant conjectures in matrices, number theory, and graph theory, attracting the attention of renowned mathematicians like Paul Erdős, Ronald Graham, and Odile Favaron. Inspired by the pioneering work of Fajtlowicz, and by interactions with mathematicians who considered conjectures of GRAFFITI, we developed the TxGraffiti program, a modern conjecturing artificial intelligence named in homage to this rich history of conjectures made by GRAFFITI and now available as an interactive website.

Graph theory is an interdisciplinary field of study that has various applications in mathematical modeling and computer science. Research in graph theory depends on the creation of not only theorems but also conjectures. Conjecture-refuting algorithms attempt to refute conjectures by searching for counterexamples to those conjectures, often by maximizing certain score functions on graphs. This study proposes a novel conjecture-refuting algorithm, referred to as the adaptive Monte Carlo search (AMCS) algorithm, obtained by modifying the Monte Carlo tree search algorithm. Evaluated based on its success in finding counterexamples to several graph theory conjectures, AMCS outperforms existing conjecture-refuting algorithms. The algorithm is further utilized to refute six open conjectures, two of which were chemical graph theory conjectures formulated by Liu et al. in 2021 and four of which were formulated by the AutoGraphiX computer system in 2006. Finally, four of the open conjectures are strongly refuted by generalizing the counterexamples obtained by AMCS to produce a family of counterexamples. It is expected that the algorithm can help researchers test graph-theoretic conjectures more effectively.

We demonstrate how Monte Carlo Search (MCS) algorithms, namely Nested Monte Carlo Search (NMCS) and Nested Rollout Policy Adaptation (NRPA), can be used to build graphs and find counter-examples to spectral graph theory conjectures in minutes.

We initiate the study of the inherent tradeoffs between the size of a neural network and its robustness, as measured by its Lipschitz constant. We make a precise conjecture that, for any Lipschitz activation function and for most datasets, any two-layers neural network with $k$ neurons that perfectly fit the data must have its Lipschitz constant larger (up to a constant) than $\sqrt{n/k}$ where $n$ is the number of datapoints. In particular, this conjecture implies that overparametrization is necessary for robustness, since it means that one needs roughly one neuron per datapoint to ensure a $O(1)$-Lipschitz network, while mere data fitting of $d$-dimensional data requires only one neuron per $d$ datapoints. We prove a weaker version of this conjecture when the Lipschitz constant is replaced by an upper bound on it based on the spectral norm of the weight matrix. We also prove the conjecture for the ReLU activation function in the high-dimensional regime $n \approx d$, and for a polynomial activation function of degree $p$ when $n \approx d^p$. We complement these findings with experimental evidence supporting the conjecture.

We present a proof of a combinatorial conjecture from the second author's Ph.D. thesis. The proof relies on binomial and multinomial sums identities. We also discuss the relevance of the conjecture in the context of PAC-Bayesian machine learning.

A primary goal of computer science is to understand which problems can be solved by efficient algorithms. Given the formidable difficulty of proving unconditional computational hardness, stateof-the-art results typically rely on unproven conjectures. While many such results rely only upon the widely-believed conjecture P NP, other results have only been proven under stronger assumptions such as the unique games conjecture [Kho02, Kho05], the exponential time hypothesis [IP01], the learning with errors assumption [Reg09], or the planted clique hypothesis [Jer92, BR13]. It has also been fruitful to conjecture that a specific algorithm (or limited class of algorithms) is optimal for a suitable class of problems. This viewpoint has been particularly prominent in the study of average-case noisy statistical inference problems, where it appears that optimal performance over a large class of problems can be achieved by methods such as the sum-of-squares hierarchy (see [RSS18]), statistical query algorithms [Kea93, BFJ 94], the approximate message passing framework [DMM09, LKZ15], and low-degree polynomials [HS17, HKP 17, Hop18]. It is helpful to have such a conjectured-optimal meta-algorithm because this often admits a systematic analysis of hardness.